package practice_2025_10.practice_10_4;

import java.util.PriorityQueue;

class Solution {
    /**
     * 柠檬水找零
     * 贪心
     * @param bills
     * @return
     */
    public boolean lemonadeChange(int[] bills) {

        // 一开始手里没有零钱
        int fiveCount = 0, tenCount = 0, twentyCount = 0;
        for(int i = 0; i < bills.length; i++) {
            // 收入
            if (bills[i] == 5) {
                fiveCount++;
            } else if (bills[i] == 10) {
                tenCount++;
            } else if (bills[i] == 20) {
                twentyCount++;
            }
            // 需要找零
            int count = bills[i] - 5;
            if (count > 0) {
                while(count >= 20 && twentyCount > 0) {
                    count -= 20;
                    twentyCount--;
                }
                while(count >= 10 && tenCount > 0) {
                    count -= 10;
                    tenCount--;
                }
                while(count >= 5 && fiveCount > 0) {
                    count -= 5;
                    fiveCount--;
                }
            }
            // 找零成功
            if (count > 0) {
                return false;
            }
        }
        return true;
    }

    /**
     * 将数组和减半的最少操作次数
     * 贪心
     * @param nums
     * @return
     */
    public int halveArray(int[] nums) {
        // sum -> <= sum / 2
        // 减最快 -> 减最大的
        PriorityQueue<Double> queue = new PriorityQueue<Double>((v1, v2) -> v2.compareTo(v1));
        double sum = 0.0;
        for(int i = 0; i < nums.length; i++) {
            queue.add((double)nums[i]);
            sum += nums[i];
        }
        int count = 0;
        double target = sum / 2;
        while(sum > target) {
            // System.out.println(sum);
            double num = queue.poll() / 2;
            sum = sum - num;
            queue.add(num);
            count++;
        }
        return count;
    }
}